﻿#define _CRT_SECURE_NO_WARNINGS 1

//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main()
//{
//    int t = 0, n = 0;
//    vector<string> vstr;
//    cin >> t;
//    vstr.resize(t);
//    for (int i = 0; i < t; i++)
//    {
//        cin >> n;
//        vstr[i].resize(n);
//        for (int j = 0; j < n; j++)
//        {
//            cin >> vstr[i][j];
//        }
//        int left = 0, right = n - 1;
//        while (right > left)
//        {
//            if (vstr[i][left] != vstr[i][right])
//            {
//                break;
//            }
//            left++;
//            right--;
//        }
//        if (left >= right)
//        {
//            cout << "Yes" << endl;
//        }
//        else
//        {
//            cout << "No" << endl;
//        }
//    }
//    return 0;
//}


//礼物的最大价值（动态规划的新思路，需要学习）
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param grid int整型vector<vector<>>
//     * @return int整型
//     */
//    int maxValue(vector<vector<int> >& grid)
//    {
//        for (int i = 1; i < grid[0].size(); i++)
//        {
//            grid[0][i] += grid[0][i - 1];
//        }
//        for (int i = 1; i < grid.size(); i++)
//        {
//            grid[i][0] += grid[i - 1][0];
//        }
//        for (int i = 1; i < grid.size(); i++)
//        {
//            for (int j = 1; j < grid[0].size(); j++)
//            {
//                if (grid[i - 1][j] > grid[i][j - 1])
//                {
//                    grid[i][j] += grid[i - 1][j];
//                }
//                else
//                {
//                    grid[i][j] += grid[i][j - 1];
//                }
//            }
//        }
//        return grid[grid.size() - 1][grid[0].size() - 1];
//    }
//};


//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main()
//{
//    int t = 0, n = 0;
//    cin >> t;
//    for (int i = 0; i < t; i++)
//    {
//        cin >> n;
//        vector<string> vstr(n);
//        for (int j = 0; j < n; j++)
//        {
//            cin >> vstr[j];
//        }
//
//        int left = 0, right = n - 1;
//        while (right > left)
//        {
//            int k = 0;
//            while (k < vstr[right].size())
//            {
//                if (vstr[left].find(vstr[right][k]) != string::npos)
//                {
//                    break;
//                }
//                k++;
//            }
//            if (k == vstr[right].size())
//            {
//                break;
//            }
//
//            left++;
//            right--;
//        }
//
//        if (left >= right)
//        {
//            cout << "Yes" << endl;
//        }
//        else
//        {
//            cout << "No" << endl;
//        }
//    }
//    return 0;
//}


//#include <iostream>
//#include <algorithm>
//using namespace std;
//int MaxCount(int x, int y)
//{
//    int m = max(x, y);
//    int n = min(x, y);
//    int r = m % n;
//    while (r)
//    {
//        m = n;
//        n = r;
//        r = m % n;
//    }
//    return n;
//}
//
//int main()
//{
//    int n = 0;
//    long long x = 0, y = 0;
//    cin >> n >> x;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> y;
//        if (x >= y)
//        {
//            x += y;
//        }
//        else
//        {
//            x += MaxCount(x, y);
//        }
//    }
//    cout << x << endl;
//    return 0;
//}